1. Field of the Invention
An object of the present invention is a method of cryptography known as a public key method based on the discrete logarithm, making use of a variable modulo p.
It can be applied in the generation of digital signatures of messages or in a transfer of authentication between two entities.
In such procedures, security is based on the fact that it is extremely difficult to reverse certain functions and more particularly the discrete logarithm.
Given the mathematical relationship y=g.sup.x modulo p which shall hereinafter be written as y=g.sup.x modp (which means that y is the remainder of the division of g.sup.x by p), this problem consists in finding x when p, g and y are known. With the present state of knowledge, this problem is impossible to resolve once the size of p reaches 512 bits or goes beyond it and once the size of x reaches 128 bits or goes beyond it.
In such systems, there is generally an authority that gives the large-sized number p constituting the modulus. The authority also chooses an integer g, called the base, such that the set generated by g, namely the set formed by the numbers g.sup.x modp for x belonging to the interval 0, p-1! is a subset of maximum size, at least 2.sup.128.
The parameters p and g are said to be "public", that is, they are given by the authority to all the users coming under this authority.
According to certain variants, these parameters are chosen individually by each user and, in this case, form an integral part of its public key.
2. Description of the Related Art
A major drawback of the implementation of cryptographic systems lies in the need for relatively large computation and storage means owing to the complex computations that are performed.
Indeed, the computation of the variable g.sup.k modp consists of the performance of modular multiplication operations and this is costly in terms of computation time and memory space. In simple electronic devices that use only standard microprocessors, this type of operation can hardly be performed.
For electronic devices possessing a processor that is specialized for this type of commutation, it is nevertheless desirable to limit the computation time and the memory space needed for the intermediate results.
Indeed, it is in general relatively costly to compute the variable g.sup.k modp by the standard square-multiply or SQM method since it is equivalent on an average to 3/2 Log.sub.2 (p) multiplication operations.
According to this method, a computation is made of all the powers of g, namely when k has a length of n bits, all the squares:
g.sup.20, g.sup.21, . . . g.sup.2n, PA1 forming a data base containing a fixed number of exponents and the corresponding powers, PA1 then for each exchange of signals: PA1 forming a fixed data base containing m random values x.sub.i and the corresponding variables z.sub.i such that z.sub.i =g.sup.xi modp, PA1 generating an exponent k necessary for each signature by carrying out a random linear combination of the values x.sub.i of the base, PA1 computing the variable g.sup.k modp on the basis of the variables z.sub.i pertaining to the values x.sub.i that come into play in the combination, PA1 using this variable in the exchanges of signals with another entity. PA1 forming an open-ended data base containing n random values of exponents and their power (k.sub.i, g.sup.k i modp), PA1 generating a new exponent k.sub.i+1 necessary for a signature by carrying out a random linear combination of the n values k.sub.i, PA1 computing the variable g.sup.k i+1 modp by obtaining the product of the powers of g.sup.k of the linear combination, PA1 updating the base of the exponents and the power values, PA1 using this variable in the exchanges of signals with another entity.
According to the simple "square-multiply" method, g.sup.k requires n/2 multiplication operations and n squares.
A method proposed by E. BRICKELL et al., known as the BGCW method, reduces the number of multiplication operations in the case of the square-multiply method but introduces a need for the storage of numerous precomputed constants and hence the need to have available a quantity of storage memories that is extremely disadvantageous.